package chunzhao.Jun_26;

/**
 * @Classname PolygonReverse
 * @Description TODO
 * @Date 2024/1/26 19:51
 * @Created by ZHL17
 */

/**
 * 多边形翻转问题
 * 一个正八边形，每条边有0，1两种状态，每次改变一条边的状态会同时改变与它相邻的边的状态，输入八个数作为八边形的初始状态，问最少多少步可以把所有边都置为0？
 */
public class PolygonReverse {
    private static int minV = Integer.MAX_VALUE;
    public static void main(String[] args) {
         int[] status = {1,0,1,0,0,0,0,0};
        boolean[] flag = new boolean[8];
         dfs(status, flag, 0, 0, status.length);
        System.out.println(minV);
    }


    public static void dfs(int[] status, boolean[] flag, int count, int id, int len) {
        if (id == status.length) {
            if (isAllZero(status)) {
                minV = Math.min(minV, count);
            }
            return ;
        }
        if (isAllZero(status)) {
            minV = Math.min(minV, count);
        }

        for (int i = id; i < status.length; i++) {
            if (flag[i]) continue;
            flag[i] = true;
            status[i] = 1 - status[i];
            status[(i + 1) % len] = 1 - status[(i + 1) % len];
            if (i == 0) {
                status[i - 1 + len] = 1 - status[i - 1 + len];
            } else {
                status[i - 1] = 1 - status[i - 1];
            }
            dfs(status,flag,count + 1, i + 1, len);

            flag[i] = false;
            status[i] = 1 - status[i];
            status[(i + 1) % len] = 1 - status[(i + 1) % len];
            if (i == 0) {
                status[i - 1 + len] = 1 - status[i - 1 + len];
            } else {
                status[i - 1] = 1 - status[i - 1];
            }
        }
    }
    public static boolean isAllZero(int[] status) {
        for (int i : status) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }
}
